/*
 * AVL.cpp
 *
 *  Created on: 04/06/2014
 *      Author: ruben
 */

#include "AVL.h"

AVL::AVL() {
	raiz=NULL;
	actual=NULL;
	contador=0;
	altura=0;

}

AVL::~AVL() {
	this->Podar(raiz);
}

// Poda: borrar todos los nodos a partir de uno, incluido
// Algoritmo recursivo, recorrido en postorden
void AVL::Podar(Nodo* nodo){
   if(nodo) {
      this->Podar(nodo->getHijoMayor()); // Podar izquierdo
      this->Podar(nodo->getHijoMenor());   // Podar derecho
      delete nodo;            // Eliminar nodo
      nodo = NULL;
   }
}

// Insertar un dato en el árbol AVL
bool AVL::Insertar(string palabra, int pos){


	/* lo difique a ver que pasa */
	/***********************************/
   Nodo *padre = NULL;
   int valorAux;

   actual = raiz;    // Buscar el dato en el árbol, manteniendo un puntero al nodo padre
   bool identico = false;
   while( !Vacio(actual) && !identico) {
      padre = actual;
      valorAux = palabra.compare(actual->getPalabra());

      if(valorAux > 0) actual = actual->getHijoMayor(); //si palabra > dato. derecho
      else if(valorAux <= 0) actual = actual->getHijoMenor();  //si palabra < dato, izquiedo
    //  else if (valorAux == 0) identico= true;
   }

   // Si se ha encontrado el elemento, no hago nada
/*   if(identico) {
	//   actual->setPos(pos);
	   return false;
   }
*/
   // Si padre es NULL, entonces el árbol estaba vacío, el nuevo nodo será el nodo raiz
   if(Vacio(padre)) raiz = new Nodo(palabra, pos);

   else{
	     valorAux = palabra.compare(padre->getPalabra());
	     // Si el dato es menor que el que contiene el nodo, lo insertamos en la rama izquierda
	     if(valorAux <= 0){
		     padre->setHijoMenor(new Nodo(palabra,pos,padre));  //izquierdo
		      Equilibrar(padre, IZQUIERDO, true);
	     }
	    // Si el dato es mayor que el que contiene el nodo, lo insertamos en la rama derecha
	     else if(valorAux > 0) {
	          padre->setHijoMayor(new Nodo(palabra,pos,padre));   //derecho
	          Equilibrar(padre, DERECHO, true);
	     }
   }

   return true;
}


// Equilibrar árbol AVL partiendo del nodo nuevo
void AVL::Equilibrar(Nodo *nodo, int rama, bool nuevo)
{
   bool salir = false;

   // Recorrer camino inverso actualizando valores de FE:
   while(nodo && !salir) {

      if(nuevo)
    	  if(rama == IZQUIERDO) nodo->FE--; // Depende de si añadimos ...
      else nodo->FE++;
      else {
         if(nodo->FE == 0) salir = true;
         if(rama == IZQUIERDO) nodo->FE++; // ... o borramos
          else nodo->FE--;
      }

      if(nodo->FE == 0) salir = true; // La altura de las rama que
                                      // empieza en nodo no ha variado,
                                      // salir de Equilibrar
      else if(nodo->FE == -2) { // Rotar a derechas y salir:
         if(nodo->getHijoMenor()->FE == 1) RDD(nodo); // Rotación doble
         else RSD(nodo);                         // Rotación simple
         salir = true;
      }
      else if(nodo->FE == 2) {  // Rotar a izquierdas y salir:
         if(nodo->getHijoMayor()->FE == -1) RDI(nodo); // Rotación doble
         else RSI(nodo);                        // Rotación simple
         salir = true;
      }

      if(nodo->getPadre()){
    	  if(nodo->getPadre()->getHijoMayor() == nodo) rama = DERECHO;
    	   else rama = IZQUIERDO;
      }
         nodo = nodo->getPadre(); // Calcular FE, siguiente nodo del camino.

   }
}

// Rotación doble a derechas
void AVL::RDD(Nodo* nodo)
{
   cout << "RDD" << endl;
   Nodo *Padre = nodo->getPadre();
   Nodo *P = nodo;
   Nodo *Q = P->getHijoMenor();
   Nodo *R = Q->getHijoMayor();
   Nodo *B = R->getHijoMenor();
   Nodo *C = R->getHijoMayor();

   if(Padre)
     if(Padre->getHijoMayor() == nodo) Padre->setHijoMayor(R);
     else Padre->setHijoMenor(R);
   else raiz = R;

   // Reconstruir árbol:
   Q->setHijoMayor(B);
   P->setHijoMenor(C);
   R->setHijoMenor(Q);
   R->setHijoMayor(P);

   // Reasignar padres:
   R->padre = Padre;
   P->padre = Q->padre = R;
   if(B) B->padre = Q;
   if(C) C->padre = P;

   // Ajustar valores de FE:
   switch(R->FE) {
      case -1: Q->FE = 0; P->FE = 1; break;
      case 0:  Q->FE = 0; P->FE = 0; break;
      case 1:  Q->FE = -1; P->FE = 0; break;
   }
   R->FE = 0;
}

// Rotación doble a izquierdas
void AVL::RDI(Nodo* nodo)
{
   cout << "RDI" << endl;
   Nodo *Padre = nodo->padre;
   Nodo *P = nodo;
   Nodo *Q = P->getHijoMayor();
   Nodo *R = Q->getHijoMenor();
   Nodo *B = R->getHijoMenor();
   Nodo *C = R->getHijoMayor();

   if(Padre)
     if(Padre->getHijoMayor() == nodo) Padre->setHijoMayor(R);
     else Padre->setHijoMenor(R);
   else raiz = R;

   // Reconstruir árbol:
   P->setHijoMayor(B);
   Q->setHijoMenor(C);
   R->setHijoMenor(P);
   R->setHijoMayor(Q);

   // Reasignar padres:
   R->padre = Padre;
   P->padre = Q->padre = R;
   if(B) B->padre = P;
   if(C) C->padre = Q;

   // Ajustar valores de FE:
   switch(R->FE) {
      case -1: P->FE = 0; Q->FE = 1; break;
      case 0:  P->FE = 0; Q->FE = 0; break;
      case 1:  P->FE = -1; Q->FE = 0; break;
   }
   R->FE = 0;
}

// Rotación simple a derechas
void AVL::RSD(Nodo* nodo)
{
   cout << "RSD" << endl;
   Nodo *Padre = nodo->padre;
   Nodo *P = nodo;
   Nodo *Q = P->getHijoMenor();
   Nodo *B = Q->getHijoMayor();

   if(Padre)
     if(Padre->getHijoMayor() == P) Padre->setHijoMayor(Q);
     else Padre->setHijoMenor(Q);
   else raiz = Q;

   // Reconstruir árbol:
   P->setHijoMenor(B);
   Q->setHijoMayor(P);

   // Reasignar padres:
   P->padre = Q;
   if(B) B->padre = P;
   Q->padre = Padre;

   // Ajustar valores de FE:
   if(Q->FE == 0) {
      P->FE = -1;
      Q->FE = 1;
   } else {
      P->FE = 0;
      Q->FE = 0;
   }
}

// Rotación simple a izquierdas
void AVL::RSI(Nodo* nodo)
{
   cout << "RSI" << endl;
   Nodo *Padre = nodo->padre;
   Nodo *P = nodo;
   Nodo *Q = P->getHijoMayor();
   Nodo *B = Q->getHijoMenor();

   if(Padre)
     if(Padre->getHijoMayor() == P) Padre->setHijoMayor(Q);
     else Padre->setHijoMenor(Q);
   else raiz = Q;

   // Reconstruir árbol:
   P->setHijoMayor(B);
   Q->setHijoMenor(P);

   // Reasignar padres:
   P->padre = Q;
   if(B) B->padre = P;
   Q->padre = Padre;

   // Ajustar valores de FE:
   if(Q->FE == 0) {
      P->FE = 1;
      Q->FE = -1;
   } else {
      P->FE = 0;
      Q->FE = 0;
   }
}

// Eliminar un elemento de un árbol AVL
void AVL::Borrar(string palabra){
   Nodo *padre = NULL;
   Nodo *nodo;
   string aux;
   int ValorComparador;

   actual = raiz;
   // Mientras sea posible que el valor esté en el árbol
   while(!Vacio(actual)) {
	   ValorComparador = palabra.compare(actual->getPalabra());

      if(ValorComparador == 0) { // Si el valor está en el nodo actual
         if(EsHoja(actual)) { // Y si además es un nodo hoja: lo borramos
            if(padre) { // Si tiene padre (no es el nodo raiz)
               // Anulamos el puntero que le hace referencia
               if(padre->getHijoMayor() == actual) {
                   padre->setHijoMayor(NULL);
               } else
               if(padre->getHijoMenor() == actual) {
                   padre->setHijoMenor(NULL);
               }
            }
            else raiz = padre = NULL;
             delete actual; // Borrar el nodo
             actual = NULL;

            // El nodo padre del actual puede ser ahora un nodo hoja, por lo tanto su
            // FE es cero, pero debemos seguir el camino a partir de su padre, si existe.
            if((padre && padre->FE == 1 && padre->getHijoMayor()==NULL) ||
               (padre && padre->FE == -1 && padre->getHijoMenor()==NULL)) {
               actual = padre;
               padre = actual->padre;
            }
            if(padre){
                if(padre->getHijoMayor() == actual) Equilibrar(padre, DERECHO, false);
                else   Equilibrar(padre, IZQUIERDO, false);
            }

            return;
         }
         else { // Si el valor está en el nodo actual, pero no es hoja
            // Buscar nodo
            padre = actual;
            // Buscar nodo más izquierdo de rama derecha
            if(actual->getHijoMayor()) {
               nodo = actual->getHijoMayor();
               while(nodo->getHijoMenor()) {
                  padre = nodo;
                  nodo = nodo->getHijoMenor();
               }
            }
            // O buscar nodo más derecho de rama izquierda
            else {
               nodo = actual->getHijoMenor();
               while(nodo->getHijoMayor()) {
                  padre = nodo;
                  nodo = nodo->getHijoMayor();
               }
            }
            // Intercambiar valores de no a borrar u nodo encontrado
            // y continuar, cerrando el bucle. El nodo encontrado no tiene
            // por qué ser un nodo hoja, cerrando el bucle nos aseguramos
            // de que sólo se eliminan nodos hoja.
            aux = actual->getPalabra();
            actual->setPalabra(nodo->getPalabra());
            nodo->setPalabra(aux);
            actual = nodo;
         }
      }
      else { // Todavía no hemos encontrado el valor, seguir buscándolo
         padre = actual;
         if(ValorComparador > 0 ) actual = actual->getHijoMayor(); //derecha
         else if(ValorComparador < 0) actual = actual->getHijoMenor(); //izquierda
      }
   }
}


// Buscar un valor en el árbol

Nodo* AVL::BuscarNodoParecido(string palabra)
{
   actual = raiz;
   Nodo* match = NULL;
   unsigned longitud =0;
   unsigned longitudMax =3;
   int ValorComparador = 0;

   // Todavía puede aparecer, ya que quedan nodos por mirar
   while(!Vacio(actual)) {

	  ValorComparador = palabra.compare(actual->getPalabra());
      if( ValorComparador == 0) return actual;//match maximo

      else if(ValorComparador > 0){    // Seguir a derecha
    	  longitud = find_long_match(palabra,actual->getPalabra());  //cant de caracteres repetidos
    	  if (longitud >= longitudMax){
    		  longitudMax = longitud;
    		  match = actual;
    	  }

    	  actual = actual->getHijoMayor();
      }

      else if(ValorComparador < 0){    //seguir a izquierda
    	  longitud = find_long_match(palabra,actual->getPalabra());  //cant de caracteres repetidos
    	  if (longitud >= longitudMax){
    		  longitudMax = longitud;
    		  match = actual;
    	  }
    	  actual = actual->getHijoMenor();
      }

   }

   return match;

}


int AVL::find_long_match(string s1, string s2){
	int i =0;
		int valor = min(s1.size(),s2.size());
		while((s1[i] == s2[i]) && (valor > i))
			i++;
	return i;
}

/*
// Calcular la altura del nodo que contiene el dato dat
int AVL::Altura(const int dat)
{
   int altura = 0;
   actual = raiz;

   // Todavía puede aparecer, ya que quedan nodos por mirar
   while(!Vacio(actual)) {
      if(dat == actual->dato) return altura; // dato encontrado
      else {
         altura++; // Incrementamos la altura, seguimos buscando
         if(dat > actual->dato) actual = actual->derecho;
         else if(dat < actual->dato) actual = actual->izquierdo;
      }
   }
   return -1; // No está en árbol
}
*/
/*
// Contar el número de nodos
const int AVL::NumeroNodos()
{
   contador = 0;

   if(raiz) auxContador(raiz); // FUnción auxiliar
   return contador;
}

// Función auxiliar para contar nodos. Función recursiva de recorrido en
//   preorden, el proceso es aumentar el contador
void AVL::auxContador(Nodo *nodo)
{
   contador++;  // Otro nodo
   // Continuar recorrido
   if(nodo->izquierdo) auxContador(nodo->izquierdo);
   if(nodo->derecho)   auxContador(nodo->derecho);
}

// Calcular la altura del árbol, que es la altura del nodo de mayor altura.
const int AVL::AlturaArbol()
{
   altura = 0;

   if(raiz) auxAltura(raiz, 0); // Función auxiliar
   return altura;
}

// Función auxiliar para calcular altura. Función recursiva de recorrido en
// postorden, el proceso es actualizar la altura sólo en nodos hojas de mayor
// altura de la máxima actual
void AVL::auxAltura(Nodo *nodo, int a)
{
   // Recorrido postorden
   if(nodo->izquierdo) auxAltura(nodo->izquierdo, a+1);
   if(nodo->derecho)   auxAltura(nodo->derecho, a+1);
   // Proceso, si es un nodo hoja, y su altura es mayor que la actual del
   // árbol, actualizamos la altura actual del árbol
   if(EsHoja(nodo) && a > altura) altura = a;
}

// Función de prueba para recorridos del árbol
void Mostrar(int &d, int FE)
{
   cout << d << "(" << FE << "),";
}
*/



// Recorrido de árbol en inorden, aplicamos la función func, que tiene
// el prototipo:
// void func(int&, int);
/*
void AVL::InOrden(void (*func)(int&, int) , Nodo *nodo, bool r)
{
   if(r) nodo = raiz;
   if(nodo) {
       if(nodo->izquierdo) InOrden(func, nodo->izquierdo, false);
       func(nodo->dato, nodo->FE);
       if(nodo->derecho) InOrden(func, nodo->derecho, false);
   }
}

// Recorrido de árbol en preorden, aplicamos la función func, que tiene
// el prototipo:
// void func(int&, int);
void AVL::PreOrden(void (*func)(int&, int), Nodo *nodo, bool r)
{
   if(r) nodo = raiz;
   if(nodo) {
       func(nodo->dato, nodo->FE);
       if(nodo->izquierdo) PreOrden(func, nodo->izquierdo, false);
       if(nodo->derecho) PreOrden(func, nodo->derecho, false);
   }
}

// Recorrido de árbol en postorden, aplicamos la función func, que tiene
// el prototipo:
// void func(int&, int);
void AVL::PostOrden(void (*func)(int&, int), Nodo *nodo, bool r)
{
   if(r) nodo = raiz;
   if(nodo) {
      if(nodo->izquierdo) PostOrden(func, nodo->izquierdo, false);
      if(nodo->derecho) PostOrden(func, nodo->derecho, false);
      func(nodo->dato, nodo->FE);
   }
}
*/

